package class01

/*
	给定一个N*N的矩阵matrix, 只有0和1两种值，返回边框全是1的最大正方形的边长长度。
	如：	  x:01234
          y:
		  0	01111
		  1	01001
		  2	01001
		  3	01111
		  4	01011
	其中边框全是1的最大正方形的大小为4*4，所以返回4.
*/
func MyMaxOneBorderSize(matrix [][]int) int {
	wid := len(matrix)
	if wid < 1 {return 0}
	mLen := len(matrix[0])
	var ans int
	leftOneRecord := make([][]int, wid)
	downOneRecord := make([][]int, wid)
	for i:=0; i<wid; i++ {
		leftOneRecord[i] = make([]int, mLen)
		downOneRecord[i] = make([]int, mLen)
	}
	for i:=0; i<wid; i++ {
		for j:=mLen-1; j>=0; j-- {
			if matrix[i][j] == 1 {
				leftOneRecord[i][j] += 1
				if j + 1 < mLen {
					leftOneRecord[i][j] += leftOneRecord[i][j+1]
				}
			}
 		}
	}
	for i:=0; i<mLen; i++ {
		for j:=wid-1; j>=0; j-- {
			if matrix[j][i] == 1 {
				downOneRecord[j][i] += 1
				if j + 1 < wid {
					downOneRecord[j][i] += downOneRecord[j+1][i]
				}
			}
		}
	}
	for i:=0; i<wid; i++ {
		for j:=0; j<mLen; j++ {
			ans = max(ans, GetMaxBorder(matrix, leftOneRecord, downOneRecord, i, j))
		}
	}
	return ans
}

func GetMaxBorder(matrix [][]int, leftOneRecord [][]int, downOneRecord [][]int, i, j int) int {
	var minSize int
	if matrix[i][j] == 1 {
		minSize = min(leftOneRecord[i][j], downOneRecord[i][j])
		for minSize > 1 {
			if downOneRecord[i][j+minSize-1] >= minSize && leftOneRecord[i+minSize-1][j] >= minSize {
				return minSize
			}
			minSize--
		}
	}
	return minSize
}
